Умова задачі:
Знайти число шляхів, які відповідають деякій трійці невідємних чисел α, β, γ для матриці суміжності .
Документація:
Шляхом є послідовність вершин у графі G, яку необхідно пройти з хi в xj – вершину.
Довжиною шляху буде кількість ребер пройдених з початку шляху х[і] в кінець шляху x[j].
Число шляхів довжиною n з хі в xj – вершину дорівнює (An)ij, де А – задана матриця суміжності графа G.
Наприклад:
При запуску програма виводить нам на екран
/
Після введення потужності множини наша програма просить ввести значення матриці суміжності (у випадку введення не 1 та 0 програма вказує, що величинами повинні бути тільки 1 або 0, після чого продовжуємо роботу)
/
Ввівши множину, програма показує нам нашу матрицю суміжності і просить ввести початок шляху
/
Після введення шляху, вводимо кінець шляху, а після цього довжину шляху. В результаті програма виводить результат
/
Наша програма завершена.
Код програми:
#include <iostream>
#include <ctype.h>
using namespace std;
void CreateMatrix(int **, int &);
void PrintMatrix(int **, int &);
void MultiplayMatrix(int **, int **, int **, int &);
void EqualMatrix(int **, int **, int &);
void FindPath(int **, int **, int **, int &n);
int main()
{
char quant;
int **a, **b, **res, n;
while(true)
{
try
{
fflush(stdout);
cout << "Vvedit potuzhnist: "; cin >> quant;
if(isalpha(quant) || quant - '0' <= 0)
throw "Nedopustyme znathennja potuzhnosti!";
else
{
n = quant - '0';
break;
}
}
catch(char *e)
{
cout << e << endl;
char ch;
cout << "Natysnit knopku: "; cin >> ch;
}
}
a = new int*[n];
for(int i = 0; i < n; i++) a[i] = new int[n];
b = new int*[n];
for(int i = 0; i < n; i++) b[i] = new int[n];
res = new int*[n];
for(int i = 0; i < n; i++) res[i] = new int[n];
CreateMatrix(a, n);
PrintMatrix(a, n);
EqualMatrix(a, b, n);
FindPath(res, a, b, n);
for(int i = 0; i < n; i++) delete a[i];
delete []a;
for(int i = 0; i < n; i++) delete b[i];
delete []b;
for(int i = 0; i < n; i++) delete res[i];
delete []res;
system("pause");
return 0;
}
void CreateMatrix(int **a, int &n)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
try
{
char v;
cout << "a[" << i << "][" << j << "] = ";cin >> v;
if((v != '0') && (v != '1'))
throw "Velythyna povynna buty 1 abo 0!";
else a[i][j] = (int)(v - '0');
}
catch(const char *msg)
{
cout << "Vykluthennja: " << msg << endl;
j--;
}
}
}
}
void PrintMatrix(int **a, int &n)
{
cout << " ";
for(int l = 0; l < n; l++) cout << l << " ";
cout << endl;
for(int i = 0; i < n; i++)
{
cout << i << "|";
for(int j = 0; j < n; j++)
{
cout << a[i][j] << " ";
if(j == (n-1)) cout << endl;
}
}
}
void MultiplayMatrix(int **res, int **a, int **b, int &n)
{
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
res[k][i] = 0;
for(int j = 0; j < n; j++)
{
res[k][i] += b[k][j]*a[j][i];
}
}
}
EqualMatrix(res, b, n);
}
void FindPath(int **res, int **a, int **b,int &n)
{
char start, end, dist;
while(true)
{
try
{
cout << "Pothatok shljachu: "; cin >> start;
if(isdigit(start - '0') || start - '0' < 0 || start - '0' > n - 1)
throw "Pomylka!";
else break;
}
catch(char *e)
{
cout << e << endl;
char ch;
cout << "Natysnit knopku: "; cin >> ch;
}
}
while(true)
{
try
{
cout << "Kinez shljachu: "; cin >> end;
if(isdigit(end - '0') || end - '0' < 0 || end - '0' > n - 1)
throw "Pomylka!";
else break;
}
catch(char *e)
{
cout << e << endl;
char ch;
cout << "Natysnit knopku: "; cin >> ch;
}
}
while(true)
{
try
{
cout << "Dovzhyna shljacu: "; cin >> dist;
if(isdigit(dist - '0') || dist - '0' < 0)
throw "Pomylka!";
else break;
}
catch(char *e)
{
cout << e << endl;
char ch;
cout << "Natysnit knopku: "; cin >> ch;
}
}
cout << dist - '0' <<...
